// 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
// 第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
// 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。
// 相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，
// 第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
// 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 
// 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

const wiggleMaxLength = function (nums: number[]): number {
    // 安全检测
    if (nums.length < 1) {
        return 0;
    }
    // 初始化状态变量
    let decreasing: number = 1;
    let increasing: number = 1;
    // 状态转移方程
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            increasing = decreasing + 1;
        } else if (nums[i] < nums[i - 1]) {
            decreasing = increasing + 1;
        }
    }
    return Math.max(decreasing, increasing);
};


wiggleMaxLength([3, 3, 3, 2, 5]);

// 这种求最长子序列的题目都很容易想到使用动态规划算法来求解
// 这道题的巧妙之处在于状态变量的设置
// 上升变量表示最后趋势为上升的最长子序列区间长度
// 下降变量表示最后趋势为下降的最长子序列区间长度
// 这里巧妙地是状态转移方程，通过画图我们可以了解到
// 我们在扫描原序列的时候：
// 如果发现趋势是上升，上升变量的大小应该为下降变量的大小+1
// 反之，如果发现趋势是下降，下降变量的大小应该为上升变量的大小+1
// 通过状态转移方程，扫描完整个区间我们对上升和下降变量取最大，就可以得到最后结果。